Flash memory devices (e.g., NAND flash devices) have become increasingly popular in data storage for computer systems, mobile devices, consumer devices (e.g., cameras). In many applications, it is important for flash devices to achieve high performance to satisfy the applications demands.
In a typical flash-based subsystem, pages in flash devices may become invalidated as result of frequent writing and updating. Over time, invalid pages may populate the memory subsystem such that free or available pages become increasingly less and less and scattered within the subsystem, leading to fragmentation. To improve the performance, a process called garbage collection cleans the memory subsystem by defragmenting the pages. Garbage collection typically involves two phases: selection and collection. In the selection phase, the best candidate for garbage collection is selected. In the collection phase, the valid pages in the selected block are copied elsewhere and then the block is erased. To reduce processing time, the best candidate ideally is the block that has the most invalid pages, or the least valid pages, so that the time to copy the valid pages is the fastest, resulting in efficient garbage collection. Selecting the best candidate for erasure during garbage collection is often a time-consuming process.